The provision of negotiated Quality-of-Service (QoS) guarantees such as data transfer rate and data transfer delay to traffic generated by applications of widely different characteristics is a primary objective in packet networks. In such networks, when network resources such as communication links are shared among a plurality of network connections (also referred to as “flows”), sophisticated packet scheduling disciplines are necessary to satisfy the QoS requirements of network connections that are bandwidth- and delay-sensitive. A server in a communication system providing such QoS guarantees typically employs multiple queues, in which each queue is associated with a corresponding network connection, and uses a scheduling algorithm to control the order in which the individual queues are served.
One such sophisticated scheduling algorithm is the Generalized Processor Sharing (GPS) scheduling policy. GPS is an idealized scheme which guarantees a negotiated minimum data transfer rate to each network connection, regardless of the behavior of other connections. GPS also guarantees a negotiated maximum end-to-end data transfer delay to each connection, and ensures that all connections are served in a fair manner. During any time interval, a GPS server serves all backlogged queues, i.e., queues which have packets waiting to be transmitted, simultaneously, each with an instantaneous service rate and delay associated with the respective connection. It can be appreciated that since all connections have to be serviced simultaneously, the GPS algorithm cannot be implemented in a real-world packet network, and, therefore, is considered to be more of an ideal scheduling discipline.
A class of scheduling disciplines, called GPS-related packet schedulers, approximate the GPS scheduling policy to a certain degree and can therefore be implemented in an actual packet network. These algorithms are all based on maintaining a global function, referred to as “virtual time” or “system potential”, which is a measure of the amount of service that has been provided by a server. A server uses this global function to compute a “finishing virtual time”, also referred to as a “timestamp”, for each packet in the associated system. In this case, the timestamp is indicative of when the service of the corresponding packet should be completed. The server selects the packets for transmission based on the values of their respective timestamps, starting with the smallest value. The GPS-related packet-scheduling disciplines differ from one another in the specific function used as “virtual time”. Similarly to GPS, all of the GPS-related packet-scheduling disciplines provide a negotiated minimum data transfer rate to each network connection. The specific virtual-time function that is used by each of such disciplines determines the implementation complexity of the algorithm, the value of the maximum data transfer delay that the algorithm can provide to a connection, and whether or not the algorithm serves all connections in a fair manner. An algorithm that is of minimum complexity, provides a small value of the maximum data transfer delay to each connection, and serves all connections fairly, is highly desirable.
Further, traffic shaping has begun to gain considerable attention as a key component in the deployment of any of the emerging QoS frameworks for packet networks. In particular, a “traffic shaper” can be defined as a device that delays some or all of the packets in a traffic stream in order to bring the stream into compliance with a predetermined traffic profile (the traffic profile of a packet flow expresses the maximum amount of service that the flow is allowed to receive during a given time interval). Traffic shapers play a prominent role in the traffic conditioners that are located at the boundaries of contiguous network domains. In order to prevent a packet stream (i.e., a packet flow) from being heavily policed when entering a new domain, the egress node of the originating domain utilizes a “traffic shaper” to constrain the flow to remain within the negotiated profile.
A critical issue that remains to be solved for the effective deployment of traffic shaping in actual network nodes is the integration of “per-flow” traffic regulators in a scheduler that provides strict individual bandwidth guarantees, while also distributing access to the outgoing link of a packet multiplexer. The objective of such an integrated shaping-scheduling structure is the simultaneous enforcement of robust lower and upper bounds on the amount of service distributed to the individual flows, with upper bounds that can be either finite (for “shaped” flows) or infinite (for “unshaped” flows). The provision of “delay guarantees” on a packet-by-packet basis is not considered to be an objective, since a shaper typically operates in a context where the arrival patterns of the multiplexed flows are poorly regulated, and it is well-known that no packet-delay guarantees can be sustained for a multitude of flows that are not themselves regulated at their sources. However, the achievement of minimal latency and optimal worst-case fairness—on a per-flow basis—remains a major objective, since these properties contribute to the smoothness of the service patterns generated by the shaper.
One exemplary traffic shaper model, which will be used during the course of the description of the present invention, is defined as a “dual-leaky-bucket regulator”. A dual-leaky-bucket regulator consists of two components: (1) a Sustainable-Bit-Rate (SBR) leaky bucket, which constrains the long-term behavior of the shaped flow; and (2) a Peak-Bit-Rate (PBR) leaky bucket, which imposes a bound on the transmission rate of the flow during its bursts of activity. The SBR leaky bucket associated with a generic flow fl is specified by two parameters: a “bucket size” Bl,s and a “token rate” ρl,s. Similarly, the PBR leaky bucket associated with flow fl is also defined by a bucket size Bl,p and a token rate of ρl,p. According to the one of the available definitions of the leaky-bucket regulator, the leaky bucket remains empty when the transmission rate of the flow is persistently below the token rate, whereas an increase in the activity of the flow implies the accumulation of tokens in the bucket. When the amount of accumulated tokens hits the bucket size, the regulator forces the transmission rate of the flow to be equal to the token rate.
Flow fl maintains two state variables associated with the SBR leaky-bucket regulator: a “token level” Xl,s, which represents the number of tokens currently in use for the flow, and a “time of latest update” τl,s, which is set to the time when the state of the leaky bucket was last updated. Similar state variables Xl,p and τl,p are associated with the PBR leaky bucket. Indeed, since both leaky buckets always have their states updated at the same time, we can define τl,s=τl,p=τl. It should be noted that “tokens” are defined as time units, as used in expressing both the bucket size and the token level.
Two distinct events trigger the update of the state of a leaky bucket associated with flow fl: (1) the arrival of a packet when the flow queue is empty, and (2) the transmission of a packet. With respect to the arrival of a packet to an empty queue, consider a time tl,ak, when a packet plk arrives to the system and finds the corresponding flow fl idle. Then, the above-defined state variables are updated as follows:Xl,s=max(0,Xl,s−(tl,ak−τl))Xl,p=max(0,Xl,p−(tl,ak−τl))τl=tl,akRegarding the completion of a packet transmission, consider a time tl,dk when the server completes the transmission of a packet plk. At time tl,dk, the state variables are processed as follows:Xl,s=max(0,Xl,s−(tl,dk−τl))+llk/ρl,sXl,p=max(0,Xl,p−(tl,dk−τl))+llk/ρl,pτl=tl,dkwhere llk is defined as the length of the just-transmitted packet.
Integrated shaping-scheduling architectures are available in the prior art, but they either fail in satisfying the bandwidth requirements or the shaping constraints of the scheduled flows, or waste a considerable portion of the capacity of the outgoing link. In particular, the well-known Shaped Virtual Clock (Sh-VC) algorithm provides minimum-bandwidth and latency guarantees, and complies with the dual-leaky-bucket profiles of the configured flows. However, it cannot differentiate its shaping action on a per-flow basis, and typically suffers considerable loss of aggregate throughput under common traffic scenarios. Like any other GPS-related scheduler, the Sh-VC algorithm maintains per-flow timestamps to determine the order of transmission of packets. In particular, a flow fl that has become backlogged at time tl,ak, upon arrival of its k-th packet plk of length llk receives a new timestamp Flk based upon the following rule:       F    l    k    =            max      ⁢              (                              t                          l              ,              a                        k                    ,                      F            l                          k              -              1                                      )              +                  l        l        k                    r        l            where rl is defined as the “reserved service rate” of flow fl, and Fl0=0.
The Sh-VC algorithm implements the Smallest Eligible Finishing time First (SEFF) packet selection policy. That is, at any time ts when the server is available for the transmission of a new packet, the scheduler looks for the backlogged flow with the minimum “eligible” timestamp Femin, which is defined as follows:       F    e    min    =            min              j        ∈                  B          ⁢                      (                          t              s                        )                                ⁢          {                                                  F              j                        ⁢                                                   ⁢                          s              .              t              .                                                           ⁢                              F                j                                              -                                    l              j                                      r              j                                      ≤                  t          s                    }      where B(ts) is the set of flows that are backlogged at time ts.
At time tl,hk+1, when the transmission of packet plk is completed and packet plk+1 reaches the head of the queue, the new timestamp of flow fl is computed as:       F    l          k      +      1        =            F      l      k        +                  l        l                  k          +          1                            r        l            
Since in Sh-VC the eligibility condition is determined by the constant-rate growth of the real time t, which is independent of the evolution of the set of timestamps in the system, it is possible to have intervals of time during which no flow is “eligible” for service, so that the server remains idle. The Sh-VC scheduler is therefore non-work-conserving in principle, and shapes the individual flows at exactly their reserved service rates, independently of the associated leaky-bucket parameters. It follows that flows that are far from violating their traffic profiles keep being serviced at their minimum guaranteed rates, and the server may happen to stay idle even if “conforming” traffic is available in the flow queues. This is particularly problematic for unshaped flows, which instead should always experience work-conserving treatment.
Thus, a need remains in the art for a system that defines the order of data packet transmissions in a packet network according to parameters that are associated with both the enforcement of traffic profiles through traffic shaping and the provision of QoS guarantees through traffic scheduling.